package top.humbleyuan.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 15:54
 * @Des 柱状图中最大矩形
 */
public class LeetCode_84 {
    public static void main(String[] args) {
        // 左右找边界，O(n2)
        m1();

        // 利用栈
        m2();
    }

    public static void m1() {
        int[] heights = {2,3};

        int max = 0;
        for(int i = 0 ;i < heights.length;i++) {
            int len = 1;
            for(int j = i - 1;j >= 0;j--) {
                if(heights[j] < heights[i]) {
                    break;
                }
                len ++;
            }

            for(int j = i + 1;j < heights.length;j++) {
                if(heights[j] < heights[i]) {
                    break;
                }
                len ++;
            }
            if(max < (len * heights[i])) {
                max = len * heights[i];
            }
        }
        System.out.println(max);
    }


    public static void m2() {
        /**
         * 栈的思路：
         * 1. 栈中维护一个递增的节点index;
         * 2. 遇到非递增的情况进行pop;
         * 3. 每次进行pop时计算当前pop出的index的矩形（以当前index作为高进行左右两边拓宽）;
         * 4. width = i - top - 1;
         * 由于需要找两边第一个比当前i小的index,所以存储的是index,以便计算宽度
         * 维护递增在于递增之后我们始终知道左边的瓶颈，一旦碰到非递增就知道了右边的瓶颈，就可以计算大小
         */
        int[] heights = {2,3};

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {

            while(stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int index = stack.pop();

                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, width * heights[index]);
            }

            stack.push(i);
        }

        // 最后会剩下一个递增的stack,进行stack非空处理
        while(stack.peek() != -1) {
            int index = stack.pop();

            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, width * heights[index]);
        }

        System.out.println(maxArea);
    }
}
